 /********************************************************************************************\
 * libeds - extensible data structures library                                                *
 * Copyright (C) 2006, Dan Kruchinin, <just.asgard@gmail.com>                                 *
 *                                                                                            *
 * -> trees/rnd_tree.c                                                                        *
 * Randomized binary tree implimentation.                                                     *
 * Randomized tree isn't safe balanced, but it emulates blancing by using random() function.  *
 * Operations with this kind of tree are faster, than in self-balanced trees, because         *
 * we don't need to make rebalancing operations and hold in tree                              *
 * some extra balancing information. But exists probability, that such kind of tree can       *
 * become disbalanced, in worst case it can be just like linked list,                         *
 * so, insert or find operations will be near O(n^2) =(                                       *
 * But in most cases randomized tree will be near balances.                                   *
 * ----                                                                                       *
 * You can learn more about randomized trees here:                                            *
 * [http://www.nist.gov/dads/HTML/randomizedBinarySearchTree.html]                            *
 * ----                                                                                       *
 * ! ATTENTION: copare function is obligatory!                                                *
 *                                                                                            *
 * This library is free software; you can redistribute it and/or modify it under the terms of *
 * the GNU Lesser General Public License as published by the Free Software Foundation;        *
 * either version 2.1 of the License, or (at your option) any later version.                  *
 *                                                                                            *
 * This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;  *
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  *
 * See the GNU Lesser General Public License for more details.                                *
 *                                                                                            *
 * You should have received a copy of the GNU Lesser General Public License along with this   *
 * library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,  *
 * Boston, MA 02111-1307 USA                                                                  *
 \********************************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include "ds.h"
#include "safe_alloc.h"
#include "errors.h"
#include "trees/bin_tree.h"
#include "trees/rnd_tree.h"

static int insert(struct _bit*, void*, void*);
static int delete(struct _bit*, bit_node*);
static bit_node* find(struct _bit*, const void*);

static bit_node* __insert(struct _bit*, bit_node*, void*, void*);
static bit_node* __find(struct _bit*, bit_node*, const void*);
static int __join(struct _bit*, bit_node*);
static int __join_by_cond(struct _bit*, bit_node*, bit_node*, int);
static void __destroy_all(struct _bit*, bit_node*);
static int __join_base_check(rnd_tree*, rnd_tree*);
static bit_node* __insert_for_join(struct _bit*, bit_node*, bit_node*);

rnd_tree* rnd_create(void)
{
  rnd_tree* rnd_t;

  rnd_t = (rnd_tree*)scalloc(1, sizeof(*rnd_t));
  _bit_init_main();
  rnd_t->tree = _bit_allocate();

  BIT_REG_DEFAULT_FUNCS(rnd_t);
  rnd_t->insert = insert;
  rnd_t->delete = delete;
  rnd_t->find = find;

  return rnd_t;
}

rnd_tree* rnd_join(rnd_tree* t1, rnd_tree* t2)
{
  rnd_tree* nt;
  bit_node* jn;

  if(__join_base_check(t1, t2) < 0)
	return NULL;

  nt = rnd_create();
  nt->tree->funcs = t1->tree->funcs;
  nt->tree->flags = t1->tree->flags;

  if(RANDOM_CONDITION(t1->tree->root)) {
	nt->tree->root = t1->tree->root;
	jn = t2->tree->root;
  }
  else {
	nt->tree->root = t2->tree->root;
	jn = t1->tree->root;
  }

  /* and join it */
  if(__join(nt->tree, jn) < 0) {
	printf("--> here?\n");
	return NULL;
  }

  _bit_destroy(t1->tree);
  _bit_destroy(t2->tree);
  sfree(t1);
  sfree(t2);
  
  return nt;
}

rnd_tree* rnd_join_by_cond(rnd_tree* t1, rnd_tree* t2, void* j_key, void* j_val)
{
  rnd_tree* nt;
  bit_node* j_node;
  int ret = 0;
  
  if(__join_base_check(t1, t2) < 0)
	return NULL;

  nt = rnd_create();
  nt->tree->funcs = t1->tree->funcs;
  nt->tree->flags = t2->tree->flags;
  j_node = _bit_node_new();

  if(nt->tree->funcs.copy != NULL) {
	if(nt->tree->funcs.copy(j_node, j_key, j_val) < 0) {
	  _ds_set_errno(DSERR_SYSTEM, DS_ERRPOS_MAIN);
	  rnd_destroy(nt);
	  _bit_node_destroy(j_node);
	  
	  return NULL;
	}
  }
  else {
	j_node->key = j_key;
	j_node->value = j_val;
  }

  nt->tree->root = j_node;

  if(__join_by_cond(nt->tree, t1->tree->root, j_node, BIT_LEFT) < 0) {
	_bit_node_destroy(j_node);
	sfree(nt);
	return NULL;
  }
  if(__join_by_cond(nt->tree, t2->tree->root, j_node, BIT_RIGHT) < 0) {
	_bit_node_destroy(j_node);
	sfree(nt);
	return NULL;
  }

  _bit_destroy(t1->tree);
  _bit_destroy(t2->tree);
  sfree(t1);
  sfree(t2);

  return nt;
}

rnd_tree* rnd_split(rnd_tree* t, bit_node* new_root)
{
  rnd_tree* nt;
  bit_node* parent;

  if(t == NULL) {
	_ds_set_errno(DSERR_EMPTY_DS, DS_ERRPOS_MAIN);
	return NULL;
  }
  if(node_empty(t->tree->root) || node_empty(new_root)) {
	_ds_set_errno(DSERR_EMPTY_NODE, DS_ERRPOS_MAIN);
	return NULL;
  }
  if(t->tree->funcs.cmp == NULL) {
	_ds_set_errno(DSERR_NO_CMP_FUNC, DS_ERRPOS_MAIN);
	return NULL;
  }

  /*
   *
   * new tree should holds values and keys of the same type as it "parent tree"
   * and it should has identical flags with the parent flags
   *
   */
  nt = rnd_create();
  nt->tree->root = new_root;
  nt->tree->funcs = t->tree->funcs;
  nt->tree->flags = t->tree->flags;
  parent = new_root->parent;

  if(!node_empty(parent)) {
	if(parent->left == new_root)
	  parent->left = NULL;
	else
	  parent->right = NULL;
  }
  if(t->tree->root == new_root)
	t->tree->root = NULL;

  nt->tree->root->parent = NULL;
  /* fix number of subnodes in "parent tree" */
  parent->_nofnodes -= new_root->_nofnodes + 1;
  _bit_recount_nodes(t->tree->root);
  
  return nt;
}

void rnd_destroy(rnd_tree* t)
{
  if(t == NULL)
	return;

  __destroy_all(t->tree, t->tree->root);
  _bit_destroy(t->tree);
  sfree(t);
}

static int insert(struct _bit* tree, void* key, void* value)
{
  ds_cmp_t res;
  bit_node* tmp;

  if(tree->funcs.cmp == NULL) {
	_ds_set_errno(DSERR_NO_CMP_FUNC, DS_ERRPOS_MAIN);
	return DSERR_NO_CMP_FUNC;
  }
  /*
   * here is better use tmp, because __insert can return NULL,
   * in this case we'll lost our tree structure
   *
   */
  if((tmp = __insert(tree, tree->root, key, value)) == NULL)
	return _ds_get_errno(DS_ERRPOS_MAIN);

  tree->root = tmp;
  return 0;
}

static int delete(struct _bit* tree, bit_node* n)
{
  bit_node *repl, *child;

  if(node_empty(n))
	return 0;

  /* if one of child is empy, it will replace node, what will be deleted */
  if(node_empty(n->left) || node_empty(n->right))
	repl = n;
  /* otherwise, it will be replaced by node, that follows after it in sorted order */
  else
	repl = _bit_node_successor(n);

  /* take care about references */
  if(!node_empty(repl->left))
	child = repl->left;
  else
	child = repl->right;
  if(!node_empty(child))
	child->parent = repl->parent;

  if(!node_empty(repl->parent)) {
	bit_node* tmp = repl->parent;

	/* fix subnodes number in each node, that placed higher replace node */
	while(!node_empty(tmp)) {
	  tmp->_nofnodes--;
	  tmp = tmp->parent;
	}

	if(repl->parent->left == repl)
	  repl->parent->left = child;
	else
	  repl->parent->right = child;
  }
  if(tree->root == n) {
	if(repl != n)
	  tree->root = repl;
	else
	  tree->root = child;
  }

  /* replace indeed */
  if(repl != n) {
	repl->parent = n->parent;

	if(!node_empty(repl->parent)) {
	  if(repl->parent->left == n)
		repl->parent->left = repl;
	  else
		repl->parent->right = repl;
	}

	repl->left = n->left;
	repl->right = n->right;

	if(!node_empty(repl->left))
	  repl->left->parent = repl;
	else
	  repl->right->parent = repl;
  }
  if(tree->funcs.delete != NULL)
	tree->funcs.delete(n->key, n->value);

  _bit_node_destroy(n);
  _bit_recount_nodes(repl); /* take care about number of subnodes one more time */

  return 0;
}

static bit_node* find(struct _bit* tree, const void* key)
{
  if(tree->funcs.cmp == NULL) {
	_ds_set_errno(DSERR_NO_CMP_FUNC, DS_ERRPOS_MAIN);
	return BIT_SEARCH_ERR;
  }
  if(key == NULL)
	return NULL;

  /* use recursive find procedure */
  return __find(tree, tree->root, key);
}

/* recursive insertion procedure */
static bit_node* __insert(struct _bit* tree, bit_node* nodes, void* key, void* value)
{
  ds_cmp_t res;
  bit_node* new;

  if(node_empty(nodes)) {
	if((new = _bit_node_new()) == NULL) {
	  return NULL;
	}
	if(tree->funcs.copy != NULL) {
	  if(tree->funcs.copy(new, key, value) == DSERR_SYSTEM) {
		_ds_set_errno(DSERR_SYSTEM, DS_ERRPOS_MAIN);
		return NULL;
	  }
	}
	else {
	  new->key = key;
	  new->value = value;
	}

	return new;
  }
  /* if we have tree without keys, make compration by values */
  if(tree->flags & DS_FNOKEYS)
	res = tree->funcs.cmp(nodes->value, value);
  else
	res = tree->funcs.cmp(nodes->key, key);

  switch(res) {
  case DS_CMP_EQ:
	/* error if DS_FUK enabled, and user tries to insert duplicate key or value(if DS_FNOKEYS enabled) */
	if(tree->flags & DS_FUK) {
	  _ds_set_errno(DSERR_DUPLICATE, DS_ERRPOS_MAIN);
	  return NULL;
	}
  case DS_CMP_GRT:
	if((new = __insert(tree, nodes->left, key, value)) == NULL)
	  return NULL;

	nodes->left = new;
	nodes->_nofnodes++;
	nodes->left->parent = nodes;

	/* randomly make right rotation(for balancing) */
	if(RANDOM_CONDITION(nodes))
	  nodes = _bit_rotate_right(tree, nodes);
	
	break;
  case DS_CMP_LESS:
	if((new = __insert(tree, nodes->right, key, value)) == NULL)
	  return NULL;

	nodes->right = new;
	nodes->_nofnodes++;
	nodes->right->parent = nodes;

	/* randomly make left rotation(for balancing) */
	if(RANDOM_CONDITION(nodes))
	  nodes = _bit_rotate_left(tree, nodes);

	break;
  case DS_CMP_ERR:
	_ds_set_errno(DSERR_SYSTEM, DS_ERRPOS_MAIN);
	return NULL;
  }

  return nodes;
}

/* recursive finding procrdure */
static bit_node* __find(struct _bit* tree, bit_node* nodes, const void* key)
{
  ds_cmp_t res;
  
  if(node_empty(nodes))
	return NULL;
  if(tree->flags & DS_FNOKEYS)
	res = tree->funcs.cmp(nodes->value, key);
  else
	res = tree->funcs.cmp(nodes->key, key);

  switch(res) {
  case DS_CMP_EQ:
	return nodes; /* find! */
  case DS_CMP_GRT:
	return __find(tree, nodes->left, key);
  case DS_CMP_LESS:
	return __find(tree, nodes->right, key);
  case DS_CMP_ERR:
	_ds_set_errno(DSERR_SYSTEM, DS_ERRPOS_MAIN);
	return BIT_SEARCH_ERR;
  }

  /* not find... */
  return NULL;
}

static int __join(struct _bit* tree, bit_node* n)
{
  int ret;
  
  if(node_empty(n))
	return 0;

  /* walk through main tree */
  if((ret = __join(tree, n->left)) < 0)
	return ret;
  if((ret = __join(tree, n->right)) < 0)
	return ret;
  if((tree->root = __insert_for_join(tree, tree->root, n)) == NULL)
	return _ds_get_errno(DS_ERRPOS_MAIN);

  return 0;
}

static int __join_by_cond(struct _bit* tree, bit_node* n, bit_node* j_node, int find)
{
  bit_node *tmp, *parent = NULL;
  ds_cmp_t res;
  int ret = 0, where = -1;

  if(node_empty(n))
	return 0;
  if((ret = __join_by_cond(tree, n->left, j_node, find)) < 0)
	return ret;
  if((ret = __join_by_cond(tree, n->right, j_node, find)) < 0)
	return ret;
  
  if(tree->flags & DS_FNOKEYS)
	res = tree->funcs.cmp(j_node->value, n->value);
  else
	res = tree->funcs.cmp(j_node->key, n->key);
  if((find == BIT_LEFT) && ((res != DS_CMP_GRT) || (res != DS_CMP_EQ))) {
	if(res == DS_CMP_ERR) {
	  _ds_set_errno(DSERR_SYSTEM, DS_ERRPOS_MAIN);
	  return DSERR_SYSTEM;
	}

	_bit_node_destroy(n);
	return 0;
  }
  if((find == BIT_RIGHT) && (res != DS_CMP_LESS)) {
	if(res == DS_CMP_ERR) {
	  _ds_set_errno(DSERR_SYSTEM, DS_ERRPOS_MAIN);
	  return DSERR_SYSTEM;
	}

	_bit_node_destroy(n);
	return 0;
  }	
  if((res == DS_CMP_GRT) && (tree->flags & DS_FUK)) {
	_bit_node_destroy(n);
	return 0;
  }

  tmp = tree->root;

  while(!node_empty(tmp)) {
	parent = tmp;

	if(tree->flags & DS_FNOKEYS)
	  res = tree->funcs.cmp(tmp->value, n->value);
	else
	  res = tree->funcs.cmp(tmp->key, n->key);

	switch(res) {
	case DS_CMP_EQ:
	  if(tree->flags & DS_FUK) {
		where = -1;
		tmp = tmp->left;
		break;
	  }
	case DS_CMP_GRT:
	  tmp->_nofnodes++;
	  tmp = tmp->left;
	  where = BIT_LEFT;
	  break;
	case DS_CMP_LESS:
	  tmp->_nofnodes++;
	  tmp = tmp->right;
	  where = BIT_RIGHT;
	  break;
	case DS_CMP_ERR:
	  _ds_set_errno(DSERR_SYSTEM, DS_ERRPOS_MAIN);
	  return DSERR_SYSTEM;
	}
  }

  if(where == BIT_LEFT)
	parent->left = n;
  else if(where == BIT_RIGHT)
	parent->right = n;
  else
	return 0;

  n->parent = parent;
  n->left = n->right = NULL;
  n->_nofnodes = 0;

  return 0;
}

/* this function destroys all nodes in tree */
static void __destroy_all(struct _bit* tree, bit_node* nodes)
{
  if(node_empty(nodes))
	return;

  /* falls down at first(because "nodes" will be deleted soon) */
  __destroy_all(tree, nodes->left);
  __destroy_all(tree, nodes->right);

  if(tree->funcs.delete != NULL)
	tree->funcs.delete(nodes->key, nodes->value);

  _bit_node_destroy(nodes);
}

static int __join_base_check(rnd_tree* t1, rnd_tree* t2)
{
  if((t1 == NULL) || (t2 == NULL)) {
	_ds_set_errno(DSERR_EMPTY_DS, DS_ERRPOS_MAIN);
	return DSERR_EMPTY_DS;
  }
  if(node_empty(t1->tree->root) || node_empty(t2->tree->root)) {
	_ds_set_errno(DSERR_EMPTY_NODE, DS_ERRPOS_MAIN);
	return DSERR_EMPTY_NODE;
  }
  if((t1->tree->funcs.cmp == NULL) || (t2->tree->funcs.cmp == NULL)) {
	_ds_set_errno(DSERR_NO_CMP_FUNC, DS_ERRPOS_MAIN);
	return DSERR_NO_CMP_FUNC;
  }
  /* both trees must holds keys and values of the same type, overmore, they must have identical flags */
  if((t1->tree->funcs.cmp != t2->tree->funcs.cmp) || (t1->tree->funcs.copy != t2->tree->funcs.copy) ||
	 (t1->tree->funcs.delete != t2->tree->funcs.delete) || (t1->tree->flags != t2->tree->flags)) {
	_ds_set_errno(DSERR_DS_JDIFF, DS_ERRPOS_MAIN);
	return DSERR_DS_JDIFF;
  }

  return 0;
}

static bit_node* __insert_for_join(struct _bit* tree, bit_node* n, bit_node* jn)
{
  ds_cmp_t res;
  
  if(node_empty(n)) {
	jn->_nofnodes = 0;
	jn->left = jn->right = NULL;
	return jn;
  }

  if(tree->flags & DS_FNOKEYS)
	res = tree->funcs.cmp(n->value, jn->value);
  else
	res = tree->funcs.cmp(n->key, jn->key);

  switch(res) {
  case DS_CMP_EQ:
	if(tree->flags & DS_FUK) {
	  if((n->left = __insert_for_join(tree, n->left, jn)) == NULL)
		return NULL;
	  
	  _bit_node_destroy(n);
	  break;
	}
  case DS_CMP_GRT:
	if((n->left = __insert_for_join(tree, n->left, jn)) == NULL)
	  return NULL;

	n->_nofnodes++;
	n->left->parent = n;

	if(RANDOM_CONDITION(n))
	  n = _bit_rotate_right(tree, n);

	break;
  case DS_CMP_LESS:
	if((n->right = __insert_for_join(tree, n->right, jn)) == NULL)
	  return NULL;

	n->_nofnodes++;
	n->right->parent = n;

	if(RANDOM_CONDITION(n))
	  n = _bit_rotate_left(tree, n);

	break;
  case DS_CMP_ERR:
	_ds_set_errno(DSERR_SYSTEM, DS_ERRPOS_MAIN);
	return NULL;
  }

  return n;
}

